The present invention relates to a channel coding; and, more particularly, to a method capable of detecting and correcting errors in data encoded with a pseudo-balanced code having a higher code rate.
As is well known, the demand for a storage system capable of storing a large amount of optical data such as a motion picture film has been increased. Therefore, various types of volume holographic data storage (VHDS) systems incorporating therein a storage medium have been recently developed for realizing high density optical storage capabilities. Further, a coding technique capable of detecting and correcting errors by noisy or otherwise impaired channel has been also developed.
Convolutional codes are a class of channel codes used to mitigate the effects of channel noise in the transmission of information. A convolutional encoder in a transmitter is a finite-state machine whose operation may be described in terms of trellis. As it accepts data bits, the convolutional encoder proceeds through a sequence of states and produces an output which subsequently is used to define an output sequence of symbols that is transmitted over a noisy or otherwise impaired channel. The output sequence of symbols corresponds to a path through the trellis that describes such encoding operation.
A maximum-likelihood decoder for convolutional codes is known in the art as the Viterbi decoder. The Viterbi decoder determines the output sequence of symbols that was transmitted based on the received corrupted version of the transmitted sequence and knowledge of the code used by the encoder. This sequence corresponds to the xe2x80x9cbest pathxe2x80x9d, that is, the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example the output sequence is determined by correlating with the received version all possible transmitted code sequences corresponding to paths through the trellis and then choosing, as the xe2x80x9cmaximum likelihoodxe2x80x9d sequence, the sequence where the correlation is maximum.
As it operates, the Viterbi decoder disregards a number of paths in the trellis and considers only the so-called surviving paths as candidates for the best path. Looking backwards in time or xe2x80x9ctracing backxe2x80x9d, the surviving paths tend to merge into the same predecessor path such that the value of an earlier received symbols may be decided. For so-called continuous Viterbi decoding, at any point in time a decision is made as to the value of an earlier received symbol by tracing back along the path identified as the best path at that time.
In the VHDS systems, variations in signal strength cause problems in detection. One possible solution to the problems in detection is the use of balanced codes. A balanced code is one in which each codeword is balanced-bit and contains exactly the same number of 1""s as 0""s. Since the number of 1""s and 0""s is balanced, the brighter 50% of samples are considered to be 1""s and the dimmer 50% of the samples are considered to be 0""s. In addition, the minimum Hamming distance, the minimum number of bits by which two distinct codewords differ, is 2. In the balanced code, a change in just one bit yields an invalid codeword because the result is unbalanced. To remain in balance, at least two bits must be changed.
FIG. 1 represents a trellis 100 of a conventional rate 8:12 balanced finite-state code capable of correcting an error. Trellis 100 has a plurality of state values which describe a sequence of state transitions. That is, trellis 100 has four top level states, state a, state b, state c and state d. Likewise, trellis 100 has four bottom level states, state a, state b, state c and state d, which are the same states as the top level states. Each transition in trellis 100 represents a set of 64 balanced codewords of length 12. There are eight such sets, assigned to the transitions as shown in Table A.
Each set, S1, (i=1, 2, . . . , 8) is an arbitrary set of 64 balanced binary codewords, each codeword being represented by 12 bits of b0b1b2 . . . b11, where b1+2b2+3b3 . . . +11b11xe2x88x92i is a multiple of 12.
This code has a minimum distance of 4, which provides considerable error-detecting and correcting capability in the presence of noise. However, there is a problem in the use of the rate 8:12 balanced finite-state code. That is, the rate 8:12 balanced finite-state code scheme has a lower code rate, i.e., about 67%. Therefore, there is a need for a coding scheme having an error-correcting capability and a higher code rate.
It is, therefore, an object of the present invention to provide a coding scheme having an error-correcting capacity and a higher code rate.
In accordance with one embodiment of the present invention, there is provided a method for encoding a series of M-bit message words into a series of N-bit codewords having a bounded unbalance, a part of the message words being used to index bits and others source words, wherein the M and N are positive integer and the N is larger than the M, comprising steps of: grouping the message words to a plurality of subsets using the index bits; classifying the unbalanced codewords to a plurality of sets based on a state transition in a trellis having states and levels, each of the classified unbalanced codewords being stored at a codebook for each codeword set, respectively, the codebook having the source words, a codeword ID for each of the source words and the classified unbalanced codewords;
encoding the message words into the respective codeword in the codebook, respectively, by using the index bits of the message words and the state transition in the trellis, the codewords being selected by transition for each state at each level of the trellis based on correlations.
In accordance with another embodiment of the present invention, there is provided a method for decoding a codeword, which is encoded by the above encoding method, from a series of data word representing intensities of an analog signal, comprising steps of: receiving the data word; calculating branch metrics between the data word and each codeword in the codeword set classified by the state transition in the trellis to obtain minimum branch for each bottom states; figuring out path metric for each bottom state based on the calculated branch metrics to select a minimum path metric thereamong for each bottom state in the trellis; selecting a best path having the smallest path metric having states and decoding stages; tracing back the selected best path and decoding a codeword corresponding to a state transition into a message word by using the codeword ID in the codebook.